Search for: All records

Ensuring fairness in computational problems has emerged as a key topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It is possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a combinatorial optimization perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between two conflicting objectives. Fairness is imposed in coverage by using coloring constraints that minimizes the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are not given a priori but need to be selected to minimize the maximum color discrepancy of each individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to simultaneously approximate both fairness and coverage in this framework. 

Abstract Neural activity coordinated across different scales from neuronal circuits to large-scale brain networks gives rise to complex cognitive functions. Bridging the gap between micro- and macro-scale processes, we present a novel framework based on the maximum entropy model to infer a hybrid resting state structural connectome, representing functional interactions constrained by structural connectivity. We demonstrate that the structurally informed network outperforms the unconstrained model in simulating brain dynamics; wherein by constraining the inference model with the network structure we may improve the estimation of pairwise BOLD signal interactions. Further, we simulate brain network dynamics using Monte Carlo simulations with the new hybrid connectome to probe connectome-level differences in excitation-inhibition balance between apolipoprotein E (APOE)-ε4 carriers and noncarriers. Our results reveal sex differences among APOE-ε4 carriers in functional dynamics at criticality; specifically, female carriers appear to exhibit a lower tolerance to network disruptions resulting from increased excitatory interactions. In sum, the new multimodal network explored here enables analysis of brain dynamics through the integration of structure and function, providing insight into the complex interactions underlying neural activity such as the balance of excitation and inhibition. 

The analysis of massive datasets requires a large number of processors. Prior research has largely assumed that tracking the actual data distribution and the underlying network structure of a cluster, which we collectively refer to as the topology, comes with a high cost and has little practical benefit. As a result, theoretical models, algorithms and systems often assume a uniform topology; however this assumption rarely holds in practice. This necessitates an end-to-end investigation of how one can model, design and deploy topology-aware algorithms for fundamental data processing tasks at large scale. To achieve this goal, we first develop a theoretical parallel model that can jointly capture the cost of computation and communication. Using this model, we explore algorithms with theoretical guarantees for three basic tasks: aggregation, join, and sorting. Finally, we consider the practical aspects of implementing topology-aware algorithms at scale, and show that they have the potential to be orders of magnitude faster than their topology-oblivious counterparts. 

The analysis of massive datasets requires a large number of processors. Prior research has largely assumed that tracking the actual data distribution and the underlying network structure of a cluster, which we collectively refer to as the topology, comes with a high cost and has little practical benefit. As a result, theoretical models, algorithms and systems often assume a uniform topology; however this assumption rarely holds in practice. This necessitates an end-to-end investigation of how one can model, design and deploy topology-aware algorithms for fundamental data processing tasks at large scale. To achieve this goal, we first develop a theoretical parallel model that can jointly capture the cost of computation and communication. Using this model, we explore algorithms with theoretical guarantees for three basic tasks: aggregation, join, and sorting. Finally, we consider the practical aspects of implementing topology-aware algorithms at scale, and show that they have the potential to be orders of magnitude faster than their topology-oblivious counterparts.